
import copy
import itertools

class Solver:
    def __init__(self, leds):
        self.leds = leds
        size = len(leds)
        self.mx = self.empty_matrix(size ** 2, size ** 2 + 1)
        tridiag_mx = self.tridiagonal_matrix(size)
        identity_mx = self.identity_matrix(size)
        for i in range(size):
            self.apply_matrix(self.mx, tridiag_mx, i * size, i * size)
        for i in range(size - 1):
            self.apply_matrix(self.mx, identity_mx, i * size, (i + 1) * size)
            self.apply_matrix(self.mx, identity_mx, (i + 1) * size, i * size)

    def tridiagonal_matrix(self, size):
        mx = self.identity_matrix(size)
        for i in range(size - 1):
            mx[i][i + 1] = True
            mx[i + 1][i] = True
        return mx

    def identity_matrix(self, size):
        mx = self.empty_matrix(size, size)
        for i in range(size):
            mx[i][i] = True
        return mx

    def empty_matrix(self, x, y):
        return [[False for _ in range(y)] for _ in range(x)]

    def apply_matrix(self, dest, source, x, y):
        for i in range(len(source)):
            for j in range(len(source[0])):
                dest[x + i][y + j] = source[i][j]

    def row_echelon(self, mx):
        # for each value in the diagonal
        for i in range(len(mx)):
            #print("row echelon loop " + str(i))
            # enshure mx[i][i] is true or skip the cycle
            if not mx[i][i]:
                #print("cerco di sostituire")
                for j in range(i, len(mx)):
                    if mx[j][i]:
                        #print("sostituisco " + str(i) + "con" + str(j))
                        mx[i], mx[j] = mx[j], mx[i]
                        break
            if mx[i][i]:
                #print("azzero la colonna")
                for j in range(i + 1, len(mx)):
                    if mx[j][i]:
                        # the sum will set mx[i][j] to false
                        self.sum_rows(mx[j], mx[i])

            #self.debug_mx(mx, "matrice:")

    def row_echelon_reduced(self, mx):
        for i in reversed(range(len(mx))):
            for j in range(i):
                if mx[j][i]:
                    self.sum_rows(mx[j], mx[i])

    def sum_rows(self, dest, source):
        for i in range(len(dest)):
            dest[i] ^= source[i]

    #fixme proper name
    def combinations(self, matrix):
        size = len(matrix)
        r = 0
        for i in reversed(range(len(matrix))):
            if matrix[i][i]:
                break
            else:
                matrix[i][i] = True
                r += 1
#        print("begin")
        for c in itertools.product(*([[True, False]] * r)):
#            print([int(e) for e in c])
            mx = copy.deepcopy(matrix)
            for i in range(1, len(c) + 1):
                mx[-i][-1] = c[i-1]
            yield mx

    def solution_length(self, mx):
        n = 0
        for row in mx:
            if row[-1]:
                n += 1
        return n

    def mark_solution(self):
        matrix = copy.deepcopy(self.mx)
        size = len(self.leds)
        for i in range(size):
            for j in range(size):
                active = self.leds[i][j].active
                matrix[j * size + i][size ** 2] = active
#        self.debug_mx(matrix, "matrice iniziale")
        self.row_echelon(matrix)
#        self.debug_mx(matrix, "row")
        self.row_echelon_reduced(matrix)
#        self.debug_mx(matrix, "row ridotta")
        # infinite is bigger than any number
        length = float("inf")
        for mx in self.combinations(matrix):
#            print("prima")
#            for row in mx:
#                print([int(n) for n in row])
            self.row_echelon_reduced(mx)
#            print("dopdopoo")
#            for row in mx:
#                print([int(n) for n in row])
            l = self.solution_length(mx)
#            print(l)
            if l < length:
                length = l
                matrix = mx

        for i in range(size):
            for j in range(size):
                led = self.leds[i][j]
                led.mark = bool(int(matrix[j * size + i][size ** 2]))

    def debug_mx(self, mx, msg):
        print(msg)
        for row in mx:
            print([int(n) for n in row])

